# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
    def Insert(self, num):
        # write code here
        self.stack.append(num)
        if len(self.stack) > 1:
            index = len(self.stack) - 1

            for i in range(len(self.stack)-2, -1, -1):
                if self.stack[index] >= self.stack[i]:
                    break
                else:
                    self.stack[index], self.stack[i] = self.stack[i], self.stack[index]
                    index = i


    def GetMedian(self):
        # write code here
        if len(self.stack) % 2:
            return self.stack[len(self.stack)//2]
        else:
            return (self.stack[len(self.stack)//2-1] + self.stack[len(self.stack)//2])/2


test = Solution()
test.Insert(5)
print(test.GetMedian())
print(test.stack)
print('=====================================')
test.Insert(2)
print(test.GetMedian())
print(test.stack)
print('=====================================')
test.Insert(3)
print(test.GetMedian())
print(test.stack)
print('=====================================')
test.Insert(4)
print(test.GetMedian())
print(test.stack)
print('=====================================')
test.Insert(1)
print(test.GetMedian())
print(test.stack)
print('=====================================')
test.Insert(6)
print(test.GetMedian())
print(test.stack)
print('=====================================')
test.Insert(7)
print(test.GetMedian())
print(test.stack)
print('=====================================')
test.Insert(0)
print(test.GetMedian())
print(test.stack)
print('=====================================')
test.Insert(8)
print(test.GetMedian())
print(test.stack)